import java.util.HashMap;
import java.util.Map;

public class Test {
    public String minWindow(String s, String t) {
        // 边界条件处理
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }

        // 第一个哈希表：存储需要的字符及其数量
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // 第二个哈希表：存储当前窗口中的字符及其数量
        Map<Character, Integer> window = new HashMap<>();

        int left = 0, right = 0;  // 滑动窗口的左右指针
        int valid = 0;  // 记录当前窗口中满足需求的字符种类数
        int start = 0, len = Integer.MAX_VALUE;  // 记录结果的起始位置和长度

        while (right < s.length()) {
            // 移动右指针，扩大窗口
            char c = s.charAt(right);
            right++;

            // 如果当前字符是需要的，更新窗口中的计数
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 如果当前字符的数量刚好满足需求，valid加1
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 当所有字符都满足需求时，尝试收缩窗口
            while (valid == need.size()) {
                // 更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                // 移动左指针，缩小窗口
                char d = s.charAt(left);
                left++;

                // 如果移除的字符是需要的，更新窗口计数和valid
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        // 返回结果
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }


    public String minWindow1(String ss, String tt){
        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();
        int[] hash1=new int[128];//统计字符t中字符的频次
        int kinds=0;//标记种类
        for(char ch:t){
            if(hash1[ch]++==0)kinds++;//拿出每一个字符，没有出现过就种类加1
        }
        int[] hash2=new int[128];//标记要遍历的s(窗口中的字符频次)
        int len=Integer.MAX_VALUE;
        int begin=-1;//标记起始位置
        int count=0;
        for (int left = 0,right=0; right < s.length; right++) {
            char in=s[right];
            //进窗口
            if(++hash2[in]==hash1[in])count++;//维护count,两个都存在当前字符就数量统计加1
            while(kinds==count){//判断
                if(right-left+1<len){//更新结果
                    begin=left;
                    len=right-left+1;
                }
                //出窗口
                char out=s[left++];
                if(hash2[out]--==hash1[out]){
                    count--;
                }
            }
        }
        if(begin==-1)return new String();
        else return ss.substring(begin,begin+len);
    }
    public String minWindow2(String ss, String tt){
        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();
        Map<Character,Integer> hash1=new HashMap<>();//统计字符t中字符的频次
        for(char ch:t){
            hash1.put(ch,hash1.getOrDefault(ch,0)+1);
        }
        int kinds= hash1.size();//标记种类
        Map<Character,Integer> hash2=new HashMap<>();//标记要遍历的s(窗口中的字符频次)
        int len=Integer.MAX_VALUE;
        int begin=-1;//标记起始位置
        int count=0;
        for (int left = 0,right=0; right < s.length; right++) {
            char in=s[right];
            //进窗口
            hash2.put(in, hash2.getOrDefault(in, 0) + 1);
            if (hash1.containsKey(in) && hash2.get(in).equals(hash1.get(in))) {
                count++;
            }
            while(kinds==count){//判断
                if(right-left+1<len){//更新结果
                    begin=left;
                    len=right-left+1;
                }
                //出窗口
                char out=s[left++];
                if (hash1.containsKey(out)) {
                    // 如果移除前频率刚好满足要求，需要减少count
                    if (hash2.get(out).equals(hash1.get(out))) {
                        count--;
                    }
                    // 更新窗口中该字符的频率
                    hash2.put(out, hash2.get(out) - 1);
                }
            }
        }
        if(begin==-1)return new String();
        else return ss.substring(begin,begin+len);
    }
    public static void main(String[] args) {
        Test solution = new Test();
        System.out.println(solution.minWindow2("ADOBECODEBANC", "ABC")); // 输出 "BANC"
        System.out.println(solution.minWindow2("a", "a")); // 输出 "a"
        System.out.println(solution.minWindow2("a", "aa")); // 输出 ""
    }
}
